439 - Knight moves/439.cpp

   1 #include <iostream>
   2 #include <set>
   3 #include <queue>
   4
   5 using namespace std;
   6
   7 typedef pair<int, int> point;
   8
   9 int dj[] = {-2, -1, +1, +2, +2, +1, -1, -2};
  10 int di[] = {-1, -2, -2, -1, +1, +2, +2, +1};
  11
  12 int main(){
  13   string s, t;
  14   while (cin >> s >> t){
  15     point start(s[0]-'a', s[1]-'1');
  16     point end(t[0]-'a', t[1]-'1');
  17
  18     set<point> visited;
  19     queue<pair<point, int> > q;
  20     q.push(make_pair(start, 0));
  21
  22     while (!q.empty()){
  23       int dist = q.front().second;
  24       point u = q.front().first;
  25       q.pop();
  26       if (0 <= u.first && u.first < 8 &&
  27           0 <= u.second && u.second < 8 && !visited.count(u)){
  28         //cout << "Visiting " << u.first << " " << u.second << endl;
  29         if (u == end){
  30           cout << "To get from "<<s<<" to "<<t<<" takes "<<dist<<" knight moves." << endl;
  31           break;
  32         }
  33         visited.insert(u);
  34         for (int k=0; k<8; ++k){
  35           q.push(make_pair(point(u.first + di[k], u.second + dj[k] ), dist + 1));
  36         }
  37       }
  38     }
  39   }
  40   return 0;
  41 }